package algorithm.templates;

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * @author Seon
 * @date 2023/4/9
 */
@Slf4j
public class BFSTemplate {
    /**
     * BFS的实现方法：
     * 1.首节点进入队列
     * 2.每个队首节点开始四个方向的轮询
     * 3.轮询后出队列，队列空后，无结果则说明无答案，否则相反。
     *
     *
     * @param CityMap int整型二维数组
     * @param n int整型
     * @param m int整型
     * @return int整型
     */
    public int countPath (int[][] CityMap, int n, int m) {
        // write code here
        // 2 是老板，即目的地，-1是障碍物，0是可以行走的空间。现在先不管题意，先把最短的路径长度写出来。
        // 如果长度是5行4列的，那么n为5，m为4；
        int[][] view = new int[n][m];
        int[] dX = {0, -1, 0, 1}; //方向默认从右边开始，顺时针旋转，轮询四个位置。
        int[] dY = {1, 0, -1, 0};
        int startX = 0, startY = 0;
        int flag = 0; // 代表是否搜寻到答案，如果有答案，那就为1
        Queue<Point> work = new ArrayDeque<>();

        // 在CityMap中搜索目标和起点的位置。
        for (int i = 0; i < CityMap.length ; i ++) {
            for (int j = 0; j < CityMap[0].length; j++) {
                if (CityMap[i][j] == 1) {
                    startX = i;
                    startY = j;
                    break;
                }
            }
        }
        Point point = new Point(startX, startY, 0);
        work.offer(point);
        while (work.size() != 0) {
            int x = work.peek().x, y = work.peek().y;
            if (CityMap[x][y] == 2) {
                flag = 1;
                System.out.println("answer step is " + work.peek().step);
                break;
            }
            for (int i = 0; i < 4; i ++) {
                int tx,ty;
                tx = x + dX[i];
                ty = y + dY[i];
                if (CityMap[tx][ty] == 0 && view[tx][ty] == 0) {
                    Point temp = new Point(tx, ty, work.peek().step + 1);
                    view[tx][ty] = 1;
                    work.offer(temp);
                }
            }
            work.poll();
        }
        if (flag == 0) {
            System.out.println("no answer");
        }
        return point.step;
    }

    /**
     * 用这个类来进行每一个节点的存储。
     */
    class Point {
        int x, y, step;
        public Point(int x, int y, int step) {
            this.x = x;
            this.y = y;
            this.step = step;
        }
    }
}
